原始题目：剑指 Offer 59 - II. 队列的最大值 (opens new window)

解题思路：

普通的队列出队入队的时间复杂度都是 $O(1)$ 的，如果说获取最大值要遍历所有的元素，那么不符合题意，因为这样 max_value 函数的时间复杂度会变成 $O(N)$。

如果采用单一变量来记录当前最大值的话，那么最大值出队后，无法确定下一个最大值。

理想状态是用另一个双端队列 $D1$ 记录最大值。$D1$ 的队头元素表示队列 $Q1$ 所有的最大值，而且 $D1$ 是一个递减队列。

如何维护这个双端队列呢？

• push_back：当一个元素 $x$ 入队 $Q1$ 的时候，判断 x 是否大于 $D1$ 的队尾元素 $a$，如果大于队尾元素，就把 $a$ 弹出（ $a$ 由于 $x$ 的存在，绝对不会是最大值了）。循环判断，直到 $D1$ 为空或者 $D1$ 的队尾元素不小于 $x$。

  比如对于队列 $1$，$1$，$1$，$2$

  不管 $1$ 有没有弹出，对于最大值是 $2$ 这个事实没有影响，也就是说，如果 $2$ 没弹出，那么就不用管 $1$ 是否为最大。

• pop_front：当一个元素 $x$ 出队 $Q1$ 的时候，判断这个 $x$ 是否等于 $D1$ 的队头元素（即 $x$ 是否为队列的最大值），如果相等就把 $D1$ 的队头元素出队，否则不出队。

代码：

class MaxQueue {

    Queue<Integer> queue;
    /**
     * 双端队列，维护一个单调递减的队列。
     * 当新插入一个元素时，检查双端队列的队尾，将所有小于新元素的元素弹出。
     * 因为有新元素的存在，所有之前小于新元素的元素都不会是最大值
     */
    Deque<Integer> deque;

    public MaxQueue() {
        queue = new LinkedList<>();
        deque = new LinkedList<>();
    }

    public int max_value() {
        return deque.isEmpty() ? -1 : deque.peekFirst();
    }

    public void push_back(int value) {
        queue.offer(value);
        while (!deque.isEmpty() && deque.peekLast() < value) {
            deque.pollLast();
        }
        deque.offerLast(value);
    }

    public int pop_front() {
        if(queue.isEmpty()){
            return -1;
        }
        if(!deque.isEmpty() && deque.peekFirst().equals(queue.peek())){
            deque.pollFirst();
        }
        return queue.poll();
    }
}

复杂度分析

• 时间复杂度$O(1)$：max_value、push_back、pop_front 方法的均摊时间复杂度均为 $O(1)$。
• 空间复杂度$O(N)$：当元素个数为 $N$ 时，双端队列最多要保存 $N$ 个元素。